#include <iostream>
#include <vector>

template <typename T>
void merge(std::vector<T> &v, int left, int right, int mid) {
  // 合并两个子数组
  std::vector<T> t(right - left + 1);
  int i = left, j = mid + 1, k = 0;
  while (i <= mid && j <= right) {
    if (v[i] > v[j]) {
      t[k++] = v[i++];
    } else {
      t[k++] = v[j++];
    }
  }
  while (i <= mid) {
    t[k++] = v[i++];
  }
  while (j <= right) {
    t[k++] = v[j++];
  }
  for (int n = 0; n < right - left + 1; n++) {
    v[left + n] = t[n];
  }
}

template <typename T> void merge_sort(std::vector<T> &v, int left, int right) {
  if (left >= right)
    return;
  // 计算left和right的中间位置
  int mid = (left + right) / 2;
  // 处理左边
  merge_sort(v, left, mid);
  merge_sort(v, mid + 1, right);
  merge(v, left, right, mid);
}

int main() {
  std::vector<int> list = {9, 8, 6, 4, 5, 3, 2, 1};
  merge_sort<int>(list, 0, 7);
  for (int &i : list) {
    std::cout << i;
  }
  std::cout << std::endl;
  return 0;
}